#include "main/utils.h"
#include "lib/list.h"
using namespace std;

ListNode* getNodeInLoop(ListNode* phead) {
  if (!phead)
    return nullptr;

  ListNode* fast_node = phead;
  ListNode* slow_node = phead;
  if (phead->next) {
    slow_node = phead->next;
  } else {
    return nullptr;
  }
  if (slow_node->next) {
    fast_node = slow_node->next;
  } else {
    return nullptr;
  }
  while (fast_node != slow_node) {
    if (slow_node->next) {
      slow_node = slow_node->next;
    } else {
      return nullptr;
    }

    if (fast_node->next) {
      fast_node = fast_node->next;
    } else {
      return nullptr;
    }
    if (fast_node->next) {
      fast_node = fast_node->next;
    } else {
      return nullptr;
    }
  }
  return fast_node;
}

ListNode* findEntryNode(ListNode* phead) {
  auto fast_node = getNodeInLoop(phead);
  if (!fast_node) {
    return nullptr;
  }
  auto slow_node = phead;
  while (fast_node != slow_node) {
    if (fast_node->next) {
      fast_node = fast_node->next;
    } else {
      return nullptr;
    }
    if (slow_node->next) {
      slow_node = slow_node->next;
    } else {
      return nullptr;
    }
  }
  return fast_node;
}

int main() {
  auto node1 = CreateNode(1);
  auto node2 = CreateNode(2);
  auto node3 = CreateNode(3);
  auto node4 = CreateNode(4);
  auto node5 = CreateNode(5);
  auto node6 = CreateNode(6);

  ConnectNode(node1, node2);
  ConnectNode(node2, node3);
  ConnectNode(node3, node4);
  ConnectNode(node4, node5);
  ConnectNode(node5, node6);
  ConnectNode(node6, node3);

  ListNode* node = findEntryNode(node1);
  cout << "The entry of loop list is: " << node->value << endl;
  
  return 0;
}
